package cn.edu.zufe.mjt.dp;

/**
 * 动态规划——最大字段和升级版
 * 题目内容
 * 输入一个长度为n的整数序列a1,a2,…,an。
 * 你的任务是恰好选择两个非空子段。
 * 子段是指原序列中的连续一段。
 * 这两个子段不能有重复部分，且他们之间相隔必须大于K。
 * 例如，选择子段[1,5]和[8,10]在区 = 2时合法，但是在K > 3时就不合法了。
 * 你需要最大化你选择的这两个子段内的整数之和。请求出这个最大值，
 */
public class LongestAscSequencePlus {
    public static void main(String[] args) {
        int[] a = {-1, 1, 2, 3, -1};
        int[] b = {5,5,-1,-2,3,-1,2,-2};

        int k = 3;
        int res = longestSequencesPlus(b, k);
        System.out.println(res);

    }

    /**
     * 解法思路，
     * 定义:udp(i)为以i为起点的最大后缀子段和,则udp(i)可以看做是将数组反过来后的dp(i)
     * 因为两个字段之间一定要间隔k个距离，如果都用以 dp(i) 为终点的子段有可能两个子段会重复。
     * 定义:pre(i)为dp(i)的前缀最大值
     * #计算最大子段和(前缀)
     * for i in range(1,n+1):dp[i]=max(a[i-1]，dp[i-1]+a[i - 1])
     * #计算最大子段和的前缀最大值for i in range(1:n+1):pre[i]=max(dp[i]，pre[i-1])
     * #计算最大子段和(后缀)
     * for i in range(n，0，-1):udp[i]=max(a[i-1]，udp[i +1]+a[i- 1])
     * #计算最终结果
     * res= float('-inf')
     * #代表负无穷，用于与其他值比较
     * for i in range(1,n-k+ 1):res=max(res，pre[i]+udp[i+k+1])
     */
    public static int longestSequencesPlus(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int[] pre = new int[n + 1];
        int[] udp = new int[n + 1];


        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
        }

        pre[0] = dp[1];
        for (int i = 1; i <= n; i++) {
            pre[i] = Math.max(dp[i], pre[i - 1]);
        }

        udp[n] = nums[n - 1];
        for (int i = n - 1; i >= 1; i--) {
            udp[i] = Math.max(nums[i - 1], udp[i + 1] + nums[i - 1]);
        }


        // [-1,1,2,3,-1] k=3
        // dp = [-1, 1, 3, 6, 5]
        // pre = [-1, 1, 3, 6, 6]
        // udp = [5, 6, 6, 3, -1]
        // res = nums[0] + nums[4] = -1 + -1 = -2, 4 - 0 = 4 > k = 3
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < n - k ; i++) {
            // 假如说 8 个数 ， k = 3，那么需要遍历的 pre 区间是 [1, 4]， 因为需要两个区间间隔至少为 3
            // 而且最后位置至少要有一个区间，那么 pre 区间就应该为 n - k - 1 个数，所以 i 的范围应该是 [1, n - k - 1]
            // 当 i = 1 时， 左区间选择只能是 [1,1]，👉区间起点应该是 1 + k + 1 = 5，右区间选择只能是 [5,5]，视频的伪代码会越界
            res = Math.max(res, pre[i] + udp[i + k + 1]);
        }

        return res;
    }


}
